740. Delete and Earn

Medium

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

大致看下来，难点在于如何解决不加相邻的数字进去。因为这一题思路可以采取之前小偷偷房子，相邻房子不偷的思路，但是区别在于，这道题给出的的nums 里两个index相邻的数，值不一定是相邻的如[2,3,100]：2，3 index相邻值也相邻，但3，100虽然index相邻但值不相邻。所以我首先想到的是把不相邻的用0填满就可以了。即mem[i]记录值为i的数字总和（同一个数出现不止一次）, 在nums里的值就为值 * 出现次数，不在就为0。不用字典，counter什么的，是因为他们的key是无序的，而这里我需要一个有序的方便从小到大遍历的list。且list的get item时间复杂度O(1)，跟字典一模样。但这样的坏处也很明显，空间占用太大，不过对于这题nums[i] is an integer in the range [1, 10000]就还好。

list 填充0

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums: return 0
        
        # initialize mem to record total point for each n in nums
        mem = [0] * (max(nums) + 1)
        for n in nums:
            mem[n] += n
        
        dp = [0] * len(mem)
        dp[0] = mem[0]
        dp[1] = mem[1]
        for i in range(2, len(dp)):
            dp[i] = max(dp[i-2] + mem[i], dp[i-1])
        return dp[-1]

n is the maximum number in the nums

Time complexity: O(n)

Space complexity: O(n)

改良版

通过写出上面的一维dp array，我们也可以发现，唯一需要用到的信息只集中于当前位置的前两格（dp[i-1], dp[i-2]）再久远的信息根本用不上，所以说根据之前动态规划的想法，我们完全可以把一维矩阵退化为两个变量（take，skip）去记录动态规划信息，正好也解决了空间复杂度的问题

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        if not nums: return 0
        
        mem = [0] * (max(nums) + 1)
        for n in nums:
            mem[n] += n
        dp = [0] * len(mem)
        
        take, skip = mem[0], mem[1]
        # dp[0] = mem[0]
        # dp[1] = mem[1]
        
        for i in range(2, len(dp)):
            take, skip = skip, max(take + mem[i], skip)
            # dp[i] = max(dp[i-2] + mem[i], dp[i-1])
        return max(take, skip)

跑完以后发现，对于空间复杂度并没有改善多少。思索了一下可能还是因为mem太暴力了。